Năm 1964, Page đứng trước cơ hội thay thế Eric Clapton để chơi cho The Yardbirds, song anh từ chối vì cho rằng điều đó là thiếu tôn trọng người bạn thân của mình[18]. Tháng 2 năm 1965, Clapton tuyên bố chia tay The Yardbirds, và Page chính thức nhận được lời đề nghị gia nhập nhóm. Song một phần vì anh chưa muốn từ bỏ sự nghiệp nghệ sĩ tự do đang rực rỡ của mình, và mặt khác cũng vì anh không hoàn toàn tự tin về tình hình sức khỏe của mình sau thời gian dài bị cảm, Page quyết định đề nghị người bạn thân Jeff Beck thay thế anh tham gia ban nhạc[27]. Ngày 16 tháng 5 năm 1966, tay trống Keith Moon, tay bass John Paul Jones, keyboard Nicky Hopkins, Beck và Page thu âm ca khúc "Beck's Bolero" tại phòng thu IBC Studios ở London. Trải nghiệm đó đã khiến Page muốn thành lập một siêu ban nhạc với Beck, Moon và tay bass John Entwistle của The Who[18]. Tuy nhiên, vì không tìm được một ca sĩ đủ chất lượng và những ràng buộc hợp đồng phức tạp khiến cho ý tưởng đổ bể. Cùng khoảng thời gian đó, Moon lần đầu tiên nhắc cái tên "Led Zeppelin" sau khi Entwistle tuyên bố rằng dự án này sẽ nổi tiếng khắp nơi như những chiếc khí cầu hàng đầu vậy[gc 3].

Chỉ vài tuần sau, Page chơi trong buổi diễn của The Yardbirds ở Oxford. Sau buổi diễn, Paul Samwell-Smith tuyên bố rời nhóm[17]. Page đề nghị được thay thế vị trí của Samwell-Smith và dễ dàng được chấp thuận. Ban đầu anh được chỉ định chơi bass, nhưng rồi sau đó chuyển sang đánh lead cùng Beck sau khi Chris Dreja chuyển sang chơi bass. Đội hình hứa hẹn đã nhanh chóng bế tắc sau khi vài mâu thuẫn cá nhân xuất hiện vì những tour diễn kéo dài cũng như việc nhóm không có được thành công thương mại rõ rệt, cho dù họ đã có cùng nhau đĩa đơn thành công "Happenings Ten Years Time Ago" (khi Page và Beck cùng tới The Yardbirds, bộ ba huyền thoại Page-Beck-Clapton chưa bao giờ chơi cùng nhau trong một đội hình chính thức, họ chỉ cùng nhau chơi lần đầu tiên trong buổi diễn từ thiện của ARMS vào năm 1983).

Sau khi Beck ra đi, ban nhạc ổn định với đội hình 4 người. Họ hoàn thiện album đầu tiên với Page chơi lead, Little Games. Album nhận được những đánh giá vô cùng trái chiều và nhìn chung không có được thành công về mặt thương mại khi chỉ đứng thứ 80 tại Billboard 200. Cho dù đã cố gắng biến sản phẩm phòng thu gần gũi với công chúng, các buổi diễn của họ lại ngày một xa lánh quan điểm đó khi chúng trở nên ngày càng heavy và experimental hơn. Những buổi diễn đó đã giới thiệu một phần những quan điểm sau này của Page với Led Zeppelin, trong đó có những lần trình diễn ca khúc "Dazed and Confused".

Sau khi Keith Relf và Jim McCarty chia tay The Yardbirds vào năm 1968, Page tuyên bố thành lập ban nhạc mới để hoàn tất tour diễn vòng quanh Scandinavia. Anh nói:

"Họ [các thành viên của The Yardbirds] không còn muốn tiếp tục, nhưng tôi thì vẫn muốn đi tiếp. Và tôi sẽ phải kéo mọi thứ qua khỏi vực sâu... những điều đã khiến cả nhóm ở bên nhau và cùng nhau chơi nhạc. Có rất nhiều nghệ sĩ tài năng quanh đây mà họ chưa được kết dính để trở thành một ban nhạc. Chìa khóa ở đây là nếu muốn tìm được ban nhạc ưng ý, nhất thiết ta cần phải đốt cháy hết tâm huyết của mình."[28]

Cuối cùng, anh chọn được ca sĩ Robert Plant và tay trống John Bonham từ nhóm Band of Joy trong khi anh đề nghị cộng tác với John Paul Jones – người trước đó cũng từng mong muốn gia nhập nhóm[29]. Trong tour diễn vòng quanh Scandinavia, ban nhạc này được đặt tên là New Yardbirds, nhưng khi nhớ lại buổi nói chuyện trước đây cùng Moon và Entwistle, Page đã đề xuất đổi tên nhóm. Quản lý Peter Grant quyết định đặt tên ban nhạc mới là "Led Zeppelin", vốn đồng âm với cụm từ "lead zeppelin"[gc 4][30].